# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def mergeKLists(self, lists: list) -> ListNode:
        def merge(node1, node2):
            dummy = ListNode(None)
            cur = dummy
            while node1 and node2:
                val1 = node1.val
                val2 = node2.val
                if val1 <= val2:
                    cur.next = node1
                    node1 = node1.next
                else:
                    cur.next = node2
                    node2 = node2.next
                cur = cur.next
            while node1:
                cur.next = node1
                node1 = node1.next
                cur = cur.next
            while node2:
                cur.next = node2
                node2 = node2.next
                cur = cur.next

            return dummy.next

        if len(lists) == 0:
            return None

        length = len(lists)
        while length > 1:
            border = length // 2 if length % 2 == 0 else length // 2 + 1
            for i in range(border):
                if i + border < length:
                    lists[i] = merge(lists[i], lists[i + border])

            length = border

        return lists[0]
